#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define N 40
int dataset[N];

void out_array(int a[],int n)
{
    int k=0;
    while (k<n) printf("%d ",a[k++]);
    printf("\n");
}

double get_aver(int dataset[], int n)
{
    double sum=0;
    for (int i=0;i<n;i++)
    {
        sum+=(dataset[i]-dataset[0]);
    }
    return sum/n+dataset[0];
}

int *find_max(int *a, int *b, int if_show_index)
{
    int *t=a, *k=a;
    while (k<=b) if(*k>*t) t=k++; else k++;
    if (if_show_index == 1) printf("The maximal %d is at %d. \n",*t,t-a);
    return t;
}

int *find_min(int *a, int *b, int if_show_index)
{
    int *t=a, *k=a;
    while (k<=b) if (*k<*t) t=k++; else k++;
    if (if_show_index==1) printf("The minimal %d is at %d. \n",*t,t-a);
    return t;
}

int* sequential_search(int *a, int *b, int target, int show_stat)
{
    int cnt=0;
    int *t=a;
    if (show_stat) printf("- Num compared: ");
    while (t<=b) //iterating over the elements
    {
        cnt++;
        if (show_stat) printf("%d ",*t);
        if (*t==target) 
        {
            printf("\n");
            printf("# Found! Total cnt: %d. Target %d is at (No.%d). \n",cnt,*t,t-a);
            return t;
            break;
        }
        t++;
    }
    printf("\n");
    printf("Target not found!\n");
    return a;
}

int* binary_search(int *a, int *b, int target, int show_stat)
{
    //array has been sorted
    int cnt = 0;
    int left=a-a,right=b-a;
    printf("- Num compared: ");
    while (left<=right)
    {
        cnt++;
        int mid=(left+right)/2;
        if (show_stat) printf("%d ",*(a+mid));
        if (*(a+mid)==target) 
        {
            printf("\n");
            printf("# Found! Total cnt: %d. Target %d is at (No.%d). \n",cnt,*(a+mid),mid);
			return a+mid;
        }
        //if (show_stat) printf("- Cnt:%3d; Num compared is %d (No.%d); \n", cnt, *(a+mid),mid);
        if (target>*(a+mid)) left=mid+1;
        else right=mid-1;
    }
    printf("\n");
    printf("Target not found!\n");
    return a;
}

void int_swap(int *a,int *b)
{
    int t=*b; *b=*a; *a=t;
}

void bubble_sort(int *a, int *b, int mode)
{
    //mode=0 ascending
    //mode=1 descending
    int *k=a,*t=b;
    while (k<=b-1)
    {
        t=a;
        while (t<=b-(k-a)-1)
        {
            if(mode==1) if(*t<*(t+1)) int_swap(t,t+1);
            if(mode==0) if(*t>*(t+1)) int_swap(t,t+1);
            t++;
        }
        k++;
    }
}

void show_help()
{
    printf("0: View help text; \n");
    printf("1: View array; \n");
    printf("2: Regenerate random array (elements smaller than 100); \n");
    printf("3: Find the average; \n");
    printf("4: Find elements larger than the average; \n");
    printf("5: Reverse the array; \n");
    printf("6: Swap the max and the min; \n");
    printf("7: Bubble sort(ascending); \n");
    printf("8: Sequential search (show stat.); \n");
    printf("9: Binary search (show stat.); \n");
    printf("10: Manually input the array; \n");
    printf("-1: Exit. \n");
}

void generate_array(int *a, int n, int max)
{
    for (int i=0;i<n;i++) 
    {
        dataset[i]=rand() % max; //generate random array;
        for (int j=0;j<i;j++) if (dataset[j]==dataset[i]) {i--; break;}
        //make sure all elements are different to eachother 
    }
}

void reverse_array(int *a,int n)
{
    for(int i = 0; i < n/2; i++) int_swap(&a[i], &a[n-i-1]);
}

int main()
{
    srand((unsigned int)time(0));
    int n,p;
    printf("Assign the num 'n' (n<=40): ");
    scanf("%d",&n);
    show_help(); 
    generate_array(dataset,n,100); 
    double aver=dataset[0];
    while (p!=-1)
    {
        scanf("%d",&p);
        switch(p)
        {
            case 0: show_help(); break;
            case 1: out_array(dataset,n); break;
            case 2: generate_array(dataset, n, 100); out_array(dataset,n); break;
            case 3: printf("The average is %f.\n", aver=get_aver(dataset,n)); break;
            case 4: 
                aver=get_aver(dataset,n); 
                for (int i=0;i<n;i++) if(dataset[i]>aver) printf("%d ",dataset[i]); 
                printf("\n"); break;
            case 5: reverse_array(dataset,n); out_array(dataset,n); break;
            case 6: 
                int_swap(find_max(dataset, dataset+n-1,1),find_min(dataset, dataset+n-1,1));
				out_array(dataset,n);  break;
            case 7: bubble_sort(dataset,dataset+n-1,0); out_array(dataset,n);break;
            case 8: for (int i=0;i<n;i++) sequential_search(dataset, dataset+n-1, dataset[i], 1); break;
            case 9: 
                bubble_sort(dataset,dataset+n-1,0); 
                for (int i=0;i<n;i++) binary_search(dataset,dataset+n-1,dataset[i],1); 
                break;
            case 10: generate_array(dataset,n,0); break;
        }
    }
    return 0;
}
